Optimization is a process to find an optimal set of parameters in order to maximize or minimize certain objectives. Without any loss of generalization, the discussion below will assume that the objective always is to be minimized. The process of optimization is usually iterative. For example, the process starts with an initial guess X0 and produces a sequence of iterates X1, X2 . . . Xk until some terminating condition is satisfied. An optimization problem in general form can be written as follows:
Minimize f(X), XεRn, fεR
where f is the objective function to be minimized and X is the vector of variables. R represents all real numbers and Rn represents all real numbers in n-dimensions.
There are many optimization techniques by which one can generate a sequence of iterations. One class of techniques that are of interest is direct search methods, specifically the ones utilizing the pattern search algorithm. Direct search methods do not require or estimate the derivative of the objective function like other classical optimization techniques. Direct search optimization techniques evaluate the objective function at a set of points around the current iterate Xk in order to choose the next iterate to use in the next iteration.
The steps in a typical pattern search algorithm are described below.
Initialization of the algorithm                X0 is the chosen initial iterate.        Δtol>0 is the tolerance on the pattern size.        Δ is set to the initial value of the pattern size.        
Body of the algorithm                Step 1: For j=0, 1, . . . k, perform steps 2 to 4 unless Δ<Δtol, then terminate loop.        Step 2: A set of points, which is called a pattern, is created around the current iterate Xj. Each point in the pattern is situated at a distance, equal to the pattern size, away from the current iterate.        Step 3: If a point within the pattern has a lower output comparing to Xj when provided as input to the objective function is found in the pattern, the point is marked as the new iterate Xj+1. Increment j by 1 and go back to step 1.        Step 4: If such a point is not found in the pattern, the pattern size Δ is reduced. The current iterate Xj is not changed and j is incremented. Go back to step 1.        
If the pattern search algorithm cannot find any improvement in the output (step 4) over the current iterate, the iteration is declared unsuccessful and the pattern size is reduced. If the iteration is unsuccessful, the algorithm checks if the current pattern size is small enough to stop the algorithm in step 1.
A pattern in a pattern search algorithm is typically constructed using a set of vectors which form a positive basis. A positive combination of viεRn: i=1, 2, . . . k can be expressed as
                    ∑                  i          =          1                k            ⁢                          ⁢                        α          i                ⁢                  v          i                      =                            α          1                ⁢                  v          1                    +      …      +                        α          k                ⁢                  v          k                      ,where αi is scalar and not less than zero. A finite set of vectors viεRn: i=1, 2, . . . k forms a positive basis set B in Rn if any vector vεRn can be expressed as a positive combination of the vectors in B.
It is common to use two kinds of positive basis sets as search directions in pattern search algorithms, namely maximal basis and minimal basis. It is known that the maximal and minimal basis set have 2n and n+1 vectors, respectively, for an n-dimensional optimization problem. FIG. 1A shows an exemplary maximal positive basis vectors in two dimensions (R2). Vector 10, vector 12, vector 14 and vector 16, which use point O as their origin and are perpendicular to their adjacent vectors, form a set of maximal positive basis vectors in two-dimensional space. On the other hand, FIG. 1B shows an exemplary minimal positive basis vectors in the same dimensions. Vector 18, having the same origin as vector 10 and vector 12, forms a 135 degrees angle with both of the vectors. The three vectors form a set of minimal positive basis vectors in two-dimensional space.
In utilizing a pattern search algorithm, most of the computation time is spent evaluating the objective function. One single evaluation of the objective function can take anywhere from a few seconds (inexpensive) to several minutes (expensive). Using a set of maximal positive basis vectors (maximum number of evaluations per iteration) in a pattern search algorithm enables one to find the optimal solution of an objective function if there is one. However, using a set of minimal positive basis vectors (minimum number of evaluations per iteration) with a pattern search algorithm can sometimes cause the algorithm to stop at a horse saddle and “think” that a solution has been found. A method is needed for pattern search algorithms that do not utilize a set of maximal positive basis vectors such that an optimal solution to an objective function can still be as reliably found as methods using a set of maximal positive basis vectors.